import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

public class BinayTree {


     class TreeNode {
         public char val;
         public TreeNode left;
         public TreeNode right;


         public TreeNode(char val) {
             this.val = val;
         }
     }
        public TreeNode  root;
        public void createTree(){
            TreeNode A = new TreeNode('A');
            TreeNode B = new TreeNode('B');
            TreeNode C = new TreeNode('C');
            TreeNode D = new TreeNode('D');
            TreeNode E = new TreeNode('E');
            TreeNode F = new TreeNode('F');
            TreeNode G = new TreeNode('G');
            TreeNode H = new TreeNode('H');
            A.left=B;
            A.right=C;
            B.left=D;
            B.right=E;
            C.left=F;
            C.right=G;
            E.right=H;
            this.root=A;

        }
        public void preOrder(TreeNode root){
            if (root ==null){
                return ;
            }
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
        public void inOrder(TreeNode root){
            if (root ==null){
                return ;
            }
            inOrder(root.left);
            System.out.print(root.val+" ");
            inOrder(root.right);
        }
        public void postOrder(TreeNode root){
            if (root ==null){
                return ;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val+" ");
        }
    List<Integer> list = new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
            if (root == null){
                return list;
            }
        list.add((int) root.val);
            preorderTraversal(root.left);
        preorderTraversal(root.right);
      return list;

    }
    int size(TreeNode root){
        if (root == null){
            return 0;
        }
         return size(root.right)+size(root.left)+1;
    }
    public static int nodeSize;
    void size2(TreeNode root){
        if (root ==null){
            return ;
        }
        nodeSize++;
        size2(root.left);
        size2(root.right);
    }
    public int size5 ;
    void getLeafNodeCount(TreeNode root){
        if (root ==null){return;
        }
        if (root.left==null&&root.right==null){
            size5++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);

    }
    public int getKLevelNodeCount(TreeNode root,int k){

        if (root == null){
            return 0;
        }
        if (k==1){
            return 1;
        }
         return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.left,k-1);

    }
    public int getHeight(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int  rightHeight = getHeight(root.right);
     return (leftHeight>rightHeight?leftHeight+1:rightHeight+1);
    }
TreeNode find(TreeNode root,int val){
        if (root==null){
            return null;
        }
         if (root.val==val){
             return root;
         }
         TreeNode ret1= find(root.left,val);
         if (ret1!=null){
             return ret1;
         }
             TreeNode ret2=find(root.right,val);
         if (ret2!=null){
             return ret2;
         }
         return null;
}
}
